# --------------------------------------------------------------------------------
# 二分归并排序


# 递归实现二分归并排序
def merge_sort(arr, ascending=True):
    """
    arr: list, 待排序的列表
    ascending: bool, 是否升序排列

    将一个列表分成两半，然后递归地对左右两半进行排序，最后合并两个有序的列表
    """
    # 输入参数不是列表
    if not isinstance(arr, list):
        raise ValueError("Input should be a list.")
    # 输入参数ascending不是bool
    if not isinstance(ascending, bool):
        raise ValueError("ascending should be a boolean.")
    # 输入参数为空列表
    if not arr:
        raise ValueError("Input list should not be empty.")
    # arr中有不可比较的元素
    if len(arr) > 1:
        first_type = type(arr[0])  # 记录下第一个元素的类型
        for item in arr:
            if not isinstance(item, first_type):
                raise ValueError(
                    "Elements in the list should be of the same type."
                )  # 添加判断元素类型是否相同
    # 递归结束条件 当列表长度小于2，直接返回
    if len(arr) < 2:
        return arr
    mid = len(arr) // 2  # 找到中间位置
    left = merge_sort(arr[:mid], ascending)  # 递归左半部分 直到长度小于2
    right = merge_sort(arr[mid:], ascending)  # 递归右半部分 直到长度小于2
    return merge(left, right, ascending)  # 合并左右两部分


# 合并两个列表并且排序
def merge(left, right, ascending):
    """
    left: list, 左半部分
    right: list, 右半部分
    ascending: bool, 是否升序排列

    函数的作用就是将两个列表分别按照升序或降序的方式合并成一个列表
    同时遍历左右两个列表,将较小或较大的元素加入到result中
    """
    # 输入参数left和right不是列表
    if not isinstance(left, list) or not isinstance(right, list):
        raise ValueError("Both left and right should be lists.")
    result = []  # 用于存放合并后的结果
    i = j = 0
    while i < len(left) and j < len(right):  # 两个列表都不为空
        if (ascending and left[i] <= right[j]) or (
            not ascending and left[i] >= right[j]
        ):  # 升序或降序
            result.append(left[i])  # 将左半部分的元素加入到result
            i += 1  # 左半部分的指针后移
        else:
            result.append(right[j])  # 将右半部分的元素加入到result
            j += 1  # 右半部分的指针后移
    result += left[i:]  # 左半部分剩余的元素加入到result
    result += right[j:]  # 右半部分剩余的元素加入到result
    return result


# 封装二分归并排序
def binary_merge_sort(arr, ascending=True):
    return merge_sort(arr, ascending)
# --------------------------------------------------------------------------------

# 插入排序
def insertion_sort(arr):
    # 遍历从1到len(arr)
    for i in range(1, len(arr)):
        key = arr[i]
        # 将arr[0..i-1]中大于key的元素向后移动一位
        j = i-1
        while j >=0 and key < arr[j] :
                arr[j+1] = arr[j]
                j -= 1
        arr[j+1] = key
    return arr


# --------------------------------------------------------------------------------


# --------------------------------------------------------------------------------
# 冒泡排序
def bubble_sort(data):


    for i in range(len(data)):  # 循环次数为数组r的长度 即外循环的趟数
        exchange = True  # 是否发生交换
        for j in range(len(data) - i - 1):
            if data[j] > data[j + 1]:  # 交换两值
                x = data[j]
                data[j] = data[j + 1]
                data[j + 1] = x
                exchange = False
        if exchange:  # 对j循环结束后返回数组 是否发生数据交换 若不交换则结束循环
            return data


# --------------------------------------------------------------------------------


# --------------------------------------------------------------------------------
# 快速排序
def QuickSortPivot(a, start, end):
    pivot = start
    #令最左边的数为基准数
    j = start + 1
    for i in range(start + 1, end + 1):
    #从start+1开始遍历当前列表的所有数
        if a[i] <= a[pivot]:
            a[i], a[j] = a[j], a[i]
            j += 1
    a[pivot], a[j - 1] = a[j - 1], a[pivot]
    pivot = j - 1
    #更新基准数的下标
    print(a[pivot], a[start:pivot], a[pivot+1:end+1])
    return pivot

def QuickSort(a, start, end):
    if start >= end:
        return
    pivot = QuickSortPivot(a, start, end)
    QuickSort(a, start, pivot - 1)
    QuickSort(a, pivot + 1, end)


# --------------------------------------------------------------------------------


# --------------------------------------------------------------------------------
# 堆排序
def heap_sort(arr):
    # 维护最大堆性质的函数
    def heapify(arr, n, i):
        largest = i            # 初始化最大值索引为根节点索引
        left = 2 * i + 1       # 左孩子索引
        right = 2 * i + 2      # 右孩子索引

        # 如果左孩子存在且大于根节点
        if left < n and arr[left] > arr[largest]:
            largest = left

        # 如果右孩子存在且大于目前最大值
        if right < n and arr[right] > arr[largest]:
            largest = right

        # 如果最大值不是根节点，则交换它们并继续维护最大堆性质
        if largest != i:
            arr[i], arr[largest] = arr[largest], arr[i]
            heapify(arr, n, largest)

    # 堆排序函数
    def sort(arr):
        n = len(arr)

        # 构建最大堆
        for i in range(n // 2 - 1, -1, -1):
            heapify(arr, n, i)

        # 依次取出堆顶元素，重新调整堆结构
        for i in range(n - 1, 0, -1):
            arr[i], arr[0] = arr[0], arr[i]   # 交换堆顶与最后一个元素
            heapify(arr, i, 0)    # 调整堆结构
        return arr
    sorted_arr = sort(arr)
    return sorted_arr
# --------------------------------------------------------------------------------



# --------------------------------------------------------------------------------
# 希尔排序
def shell_sort(data, ascending = True):
        # 输入参数不是列表
    if not isinstance(data, list):
        raise ValueError("Input should be a list.")
    # 输入参数ascending不是bool
    if not isinstance(ascending, bool):
        raise ValueError("ascending should be a boolean.")
    # 输入参数为空列表
    if not data:
        raise ValueError("Input list should not be empty.")
    # arr中有不可比较的元素
    if len(data) > 1:
        first_type = type(data[0])  # 记录下第一个元素的类型
        for item in data:
            if not isinstance(item, first_type):
                raise ValueError(
                    "Elements in the list should be of the same type."
                )  # 添加判断元素类型是否相同
            
    # 计算数据长度
    length = len(data)

    # 计算初始的间隔值，初始间隔值为数据总长度的一半
    gap = length // 2

    # 第一层循环改变gap的值对列表进行分组
    while gap > 0:
        # 对每个分组进行插入排序
        for i in range(gap, length):
            value = data[i]
            j = i - gap

            # 插入排序部分
            while j >= 0 and ((ascending and data[j] > value) or (not ascending and data[j] < value)):
                    data[j + gap] = data[j]
                    j -= gap

            data[j + gap] = value

        # 缩小增量
        gap = gap // 2

    return data


# --------------------------------------------------------------------------------

